package com.zjsru.plan2024.oneday;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @Author: cookLee
 * @Date: 2024-01-09
 * 字符串中的额外字符
 */
public class MinExtraChar {
    /**
     * 主
     * \
     * 输入：s = "leetscode", dictionary = ["leet","code","leetcode"]
     * 输出：1
     * 解释：将 s 分成两个子字符串：下标从 0 到 3 的 "leet" 和下标从 5 到 8 的 "code" 。只有 1 个字符没有使用（下标为 4），所以我们返回 1 。
     * \
     * 输入：s = "sayhelloworld", dictionary = ["hello","world"]
     * 输出：3
     * 解释：将 s 分成两个子字符串：下标从 3 到 7 的 "hello" 和下标从 8 到 12 的 "world" 。下标为 0 ，1 和 2 的字符没有使用，所以我们返回 3 。
     * \
     * @param args args
     */
    public static void main(String[] args) {
        MinExtraChar minExtraChar = new MinExtraChar();
        String s = "leetscode";
        String[] dictionary = new String[]{"leet", "code", "leetcode"};
        System.out.println(minExtraChar.minExtraChar(s, dictionary));
    }

    /**
     * 动态规划
     *
     * @param s          s
     * @param dictionary 词典
     * @return int
     */
    public int minExtraChar(String s, String[] dictionary) {
        int len = s.length();
        int[] dict = new int[len + 1];
        Arrays.fill(dict,Integer.MAX_VALUE);
        Map<String,Integer> map = new HashMap<>();
        for (String d:
             dictionary) {
            map.put(d,map.getOrDefault(d,0)+1);
        }
        //长度为0的无法分割
        dict[0] = 0;
        for (int i = 1; i <= len ; i++) {
            //假设最后一个字符作为额外字符
            dict[i] = dict[i - 1] + 1;
            for (int j = i - 1; j >= 0; j--) {
                if (map.containsKey(s.substring(j, i))) {
                    dict[i] = Math.min(dict[i], dict[j]);
                }
            }
        }
        //返回对应长度的分割次数
        return dict[len];
    }

}
